package com.gzl.exercise;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @PROJECT_NAME: exercise
 * @NAME: 数组中重复的数据
 * @DESCRIPTION: 中等
 * @USER: gaozengliang
 * @DATE: 2023/9/13
 */
public class 数组中重复的数据 {
    /**
     * 给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
     *
     * 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
     *
     * 示例 1：
     * 输入：nums = [4,3,2,7,8,2,3,1]
     * 输出：[2,3]
     *
     * 示例 2：
     * 输入：nums = [1,1,2]
     * 输出：[1]
     *
     * 示例 3：
     * 输入：nums = [1]
     * 输出：[]
     *
     * 提示：
     * n == nums.length
     * 1 <= n <= 10^5
     * 1 <= nums[i] <= n
     * nums 中的每个元素出现 一次 或 两次
     * */
    @Test
    void findDuplicates() {
        int[] nums = {4,3,2,7,8,2,3,1};//输出：[2,3]
//        int[] nums = {1};//输出：[]

        List<Integer> list = new ArrayList<>();

        for (int i=0;i<nums.length;i++){
            int index = Math.abs(nums[i])-1;
            //如果大于零，说明是第一次出现，如果已经小于零了，说明这是第二次出现
            if (nums[index]>0){
                nums[index] = -nums[index];
            }else {
                list.add(index+1);
            }
        }
        //        return list;

        System.out.print("数组：");
        for (int i=0;i<nums.length;i++){
            System.out.print(nums[i]+",");
        }
        System.out.println();
        System.out.print("重复数字：");
        for (Integer val:list){
            System.out.print(val+",");
        }

    }

    //另一种解
    @Test
    void findDuplicates2() {
        int[] nums = {4,3,2,7,8,2,3,1};//输出[2,3]
//        int[] nums = {4,3,2,7,7,2,3,1};
        int n = nums.length;
        // 将数组里的值交换到对应位置上，最后如果哪个位置的数字与它的坐标不匹配，说明这个数字重复了
        for (int i = 0; i < n; ++i) {
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
                System.out.print("交换后数组：");
                for (int j=0;j<n;j++){
                    System.out.print(nums[j]+",");
                }
                System.out.println();
            }
        }
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (nums[i] - 1 != i) {
                ans.add(nums[i]);
            }
        }
//        return ans;

        System.out.print("重复数字：");
        for (Integer val:ans){
            System.out.print(val+",");
        }
    }

    void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
